/*
 *  POJ1276: Cash Machine
 */

/*-------- Includes --------*/
#include <iostream>
#include <cstring>

using namespace std;

/*-------- Defines --------*/


/*-------- Types --------*/


/*-------- Global Variables --------*/
int cash;
int N;
int num[10];
int den[10];
int *dp;
int *ct;

/*-------- Function Prototypes --------*/


/*-------- Main Function --------*/
int main(int argc, char const *argv[])
{
    // get input
    while (cin >> cash) {
        cin >> N;

        for (int i = 0; i < N; i++)
            cin >> num[i] >> den[i];

        // allocate memory
        dp = new int[cash + 1];
        ct = new int[cash + 1];

        // initialize
        memset(dp, 0, (cash + 1) * sizeof(int));

        // dynamic programming
        for (int i = 0; i < N; i++) {
            memset(ct, 0, (cash + 1) * sizeof(int));

            for (int j = den[i]; j <= cash; j++) {
                if (dp[j] < dp[j - den[i]] + den[i] && ct[j - den[i]] < num[i]) {
                    dp[j] = dp[j - den[i]] + den[i];
                    ct[j] = ct[j - den[i]] + 1;
                }
            }
        }

        // print result
        cout << dp[cash] << endl;

        // release memory
        delete dp;
        delete ct;
    }
}

/*-------- Functions --------*/

